/* Copyright 2012 Dustin Mitchell <dmmitche [at] gmail [dot] com>
 *
 * Licensed under the GPLv3.  See included LICENSE.txt for full details.
 */

#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#include "hash.h"
#include "log.h"
#include "iterator.h"

#define LOAD_FACTOR .75

static int def_hash_func (const void *key, size_t key_size, size_t max)
{
  const uint8_t *key_bytes = (const uint8_t *)key;
  int i;
  int hash = 0;

  for (i = 0; i < key_size; ++i)
    hash += key_bytes[i];

  return hash % max;
}

static int def_key_cmp_func (const void *k1, size_t k1_size,
                             const void *k2, size_t k2_size)
{
  const uint8_t *key1_bytes = (const uint8_t *)k1;
  const uint8_t *key2_bytes = (const uint8_t *)k2;
  int i;

  if (k1_size != k2_size)
    return 0;

  for (i = 0; i < k1_size; ++i) {
    if (key1_bytes[i] != key2_bytes[i])
      return 0;
  }

  return 1;
}



static void hash_iter_next (struct iter *);
static void hash_iter_prev (struct iter *);
static int hash_iter_compare (struct iter *, struct iter *);
static void * hash_iter_deref (struct iter *);

struct iter_ops hash_iter_ops = {
  .next = hash_iter_next,
  .prev = hash_iter_prev,
  .compare = hash_iter_compare,
  .deref = hash_iter_deref
};

static int hash_iter_create (struct hash *hash, int key_hash,
                             struct hash_iter *iter)
{
  if (!hash || !iter)
    return -1;

  if (iter_create (&iter->base, &hash_iter_ops) == -1)
    return -1;

  iter->hash = hash;
  iter->cur_hash = key_hash;

  while (1) {
    if (iter->cur_hash >= iter->hash->data_size)
      break;

    if (iter->hash->data[iter->cur_hash]
        && !list_empty (iter->hash->data[iter->cur_hash]))
      break;

    ++iter->cur_hash;
  }

  if (iter->cur_hash >= iter->hash->data_size)
    return 0;

  if (list_begin (hash->data[iter->cur_hash], &iter->cur_item) == -1
      || list_end (hash->data[iter->cur_hash], &iter->end) == -1)
    return -1;

  return 0;
}

static void hash_iter_next (struct iter *iter)
{
  struct hash_iter *hiter = (struct hash_iter *)iter;

  if (!hiter)
    return;

  iter_next (ITER (&hiter->cur_item));

  if (iter_compare (ITER (&hiter->cur_item), ITER (&hiter->end)) == 1) {
    ++hiter->cur_hash;
    while (1) {
      if (hiter->cur_hash == hiter->hash->data_size)
        break;

      if (hiter->hash->data[hiter->cur_hash]
          && !list_empty (hiter->hash->data[hiter->cur_hash]))
        break;

      ++hiter->cur_hash;
    }

    if (hiter->cur_hash == hiter->hash->data_size)
      return;

    if (list_begin (hiter->hash->data[hiter->cur_hash], &hiter->cur_item) == -1
        || list_end (hiter->hash->data[hiter->cur_hash], &hiter->end) == -1)
      return;
  }
}

static void hash_iter_prev (struct iter *iter)
{
  log (LOG_WARNING, "hash iterators only support forward iteration");

  return;
}

static int hash_iter_compare (struct iter *iter1, struct iter *iter2)
{
  struct hash_iter *hiter1 = (struct hash_iter *)iter1;
  struct hash_iter *hiter2 = (struct hash_iter *)iter2;

  if (!hiter1 || !hiter2)
    return 0;

  if (hiter1->hash != hiter2->hash)
    return 0;

  if (hiter1->cur_hash != hiter2->cur_hash)
    return 0;

  if (hiter1->cur_hash == hiter1->hash->data_size)
    return 1;

  return iter_compare (ITER (&hiter1->cur_item), ITER (&hiter2->cur_item));
}

static void * hash_iter_deref (struct iter *iter)
{
  struct hash_iter *hiter = (struct hash_iter *)iter;
  struct hash_pair *pair;

  if (!hiter)
    return NULL;

  if (hiter->cur_hash == hiter->hash->data_size) {
    log (LOG_WARNING, "deref hash iterator pointing to the end of hash");
    return NULL;
  }

  pair = (struct hash_pair *)iter_deref (ITER (&hiter->cur_item));

  return pair;
}



static struct hash_pair * alloc_hash_pair (const void *key, size_t key_size,
                                           void *data)
{
  struct hash_pair *pair = NULL;

  pair = (struct hash_pair *)malloc (sizeof (struct hash_pair));
  if (!pair)
    return NULL;

  pair->key = malloc (key_size);
  if (!pair->key) {
    free (pair);
    return NULL;
  }

  memcpy (pair->key, key, key_size);

  pair->data = data;
  pair->key_size = key_size;

  return pair;
}

static void free_hash_pair (struct hash_pair *pair)
{
  free (pair->key);
  free (pair);
}

static int hash_expand (struct hash *hash)
{
  int new_size = hash->data_size * 2;
  struct hash tmp_hash;
  struct hash_iter beg, end;
  struct list **tmp_data;

  tmp_hash.data = (struct list **)malloc (new_size * sizeof (struct list *));
  if (!tmp_hash.data)
    return -1;

  tmp_hash.hfunc = hash->hfunc;
  tmp_hash.cmp_func = hash->cmp_func;
  tmp_hash.data_size = new_size;
  tmp_hash.num_entries = 0;

  if (hash_begin (hash, &beg) == -1
      || hash_end (hash, &end) == -1) {
    hash_destroy (&tmp_hash);
    return -1;
  }

  for (; !iter_compare (ITER (&beg), ITER (&end));
       iter_next (ITER (&beg))) {
    struct hash_pair *pair = (struct hash_pair *)iter_deref (ITER (&beg));

    if (!pair) {
      log (LOG_CRIT, "unexpected NULL pointer");
      hash_destroy (&tmp_hash);
      return -1;
    }

    if (hash_insert (&tmp_hash, pair->key, pair->key_size, pair->data) == -1) {
      hash_destroy (&tmp_hash);
      return -1;
    }
  }

  tmp_data = hash->data;
  hash->data = tmp_hash.data;
  tmp_hash.data = tmp_data;

  tmp_hash.data_size = hash->data_size;
  hash->data_size = new_size;

  hash_destroy (&tmp_hash);

  return 0;
}



int hash_create (struct hash *hash, hash_func hfunc, key_cmp_func cmp_func)
{
  int i;

  if (!hash)
    return -1;

  if (!hfunc)
    hfunc = def_hash_func;

  if (!cmp_func)
    cmp_func = def_key_cmp_func;

  hash->data = (struct list **)malloc (HASH_INITIAL_SIZE
                                       * sizeof (struct list *));
  if (!hash->data)
    return -1;

  hash->data_size = HASH_INITIAL_SIZE;
  hash->hfunc = hfunc;
  hash->cmp_func = cmp_func;
  hash->num_entries = 0;

  for (i = 0; i < hash->data_size; ++i)
    hash->data[i] = NULL;

  return 0;
}

void hash_destroy (struct hash *hash)
{
  int i;

  if (!hash)
    return;

  for (i = 0; i < hash->data_size; ++i) {
    if (hash->data[i]) {
      struct list_iter beg, end;

      if (list_begin (hash->data[i], &beg) == -1
          || list_end (hash->data[i], &end) == -1) {
        log (LOG_CRIT, "unable to destroy hash table, possible memory leak");
        continue;
      }

      for (; !iter_compare (ITER (&beg), ITER (&end));
           iter_next (ITER (&beg))) {
        struct hash_pair *pair = list_front (hash->data[i]);

        if (!pair) {
          log (LOG_CRIT, "unexpected NULL in hash table");
          continue;
        }

        free_hash_pair (pair);

        if (list_pop_front (hash->data[i]) == -1) {
          log (LOG_CRIT, "unable to free list");
          break;
        }
      }

      list_destroy (hash->data[i]);
      free (hash->data[i]);
    }
  }

  free (hash->data);
}

void * hash_get (struct hash *hash, const void *key, size_t key_size)
{
  int key_hash;
  struct list *key_list;
  struct list_iter beg, end;

  if (!hash || !key)
    return NULL;

  key_hash = hash->hfunc (key, key_size, hash->data_size);

  key_list = hash->data[key_hash];

  if (list_begin (key_list, &beg) == -1
      || list_end (key_list, &end) == -1)
    return NULL;

  for (; !iter_compare (ITER (&beg), ITER (&end));
       iter_next (ITER (&beg))) {
    struct hash_pair *pkey
      = (struct hash_pair *)iter_deref (ITER (&beg));

    if (hash->cmp_func (key, key_size, pkey->key, pkey->key_size) == 1)
      return pkey->data;
  }

  return NULL;
}

int hash_exists (struct hash *hash, const void *key, size_t key_size)
{
  int key_hash;
  struct list *key_list;
  struct list_iter beg, end;

  if (!hash || !key)
    return -1;

  key_hash = hash->hfunc (key, key_size, hash->data_size);

  key_list = hash->data[key_hash];
  if (!key_list)
    return 0;

  if (list_begin (key_list, &beg) == -1
      || list_end (key_list, &end) == -1)
    return -1;

  for (; !iter_compare (ITER (&beg), ITER (&end));
       iter_next (ITER (&beg))) {
    const struct hash_pair *pkey
      = (const struct hash_pair *)iter_deref (ITER (&beg));

    if (hash->cmp_func (key, key_size, pkey->key, pkey->key_size) == 1)
      return 1;
  }

  return 0;
}

int hash_insert (struct hash *hash, const void *key,
                 size_t key_size, void *data)
{
  struct hash_pair *pair;
  int key_hash;
  struct list *key_list;

  if (!hash || !key)
    return -1;

  if (hash_exists (hash, key, key_size) == 1)
    return -1;

  if (LOAD_FACTOR * hash->data_size <= hash->num_entries) {
    if (hash_expand (hash) == -1)
      return -1;
  }

  pair = alloc_hash_pair (key, key_size, data);
  if (!pair)
    return -1;

  key_hash = hash->hfunc (key, key_size, hash->data_size);

  key_list = hash->data[key_hash];
  if (!key_list) {
    key_list = (struct list *)malloc (sizeof (struct list));
    if (!key_list) {
      free_hash_pair (pair);
      return -1;
    }

    if (list_create (key_list) == -1) {
      free (key_list);
      free_hash_pair (pair);
      return -1;
    }

    hash->data[key_hash] = key_list;
  }

  if (list_push_back (key_list, pair) == -1) {
    free_hash_pair (pair);
    return -1;
  }

  ++hash->num_entries;

  return 0;
}

int hash_remove (struct hash *hash, const void *key, size_t key_size)
{
  int key_hash;
  struct list *key_list;
  struct list_iter beg, end;

  if (!hash || !key)
    return -1;

  key_hash = hash->hfunc (key, key_size, hash->data_size);

  key_list = hash->data[key_hash];
  if (!key_list)
    return 0;

  if (list_begin (key_list, &beg) == -1
      || list_end (key_list, &end) == -1)
    return -1;

  for (; !iter_compare (ITER (&beg), ITER (&end));
       iter_next (ITER (&beg))) {
    const struct hash_pair *pkey
      = (const struct hash_pair *)iter_deref (ITER (&beg));

    if (hash->cmp_func (key, key_size, pkey->key, pkey->key_size) == 1) {
      list_remove (key_list, &beg);
      --hash->num_entries;
      break;
    }
  }

  return 0;
}

int hash_begin (struct hash *hash, struct hash_iter *iter)
{
  if (!hash || !iter)
    return -1;

  return hash_iter_create (hash, 0, iter);
}

int hash_end (struct hash *hash, struct hash_iter *iter)
{
  if (!hash || !iter)
    return -1;

  return hash_iter_create (hash, hash->data_size, iter);
}
